package algorithm.leetcode.I201to400;

// 1 0 1 0 0
// 1 0 1 1 1
// 1 1 1 1 1
// 1 0 0 1 0

// dp二维数组,首行首列与原矩阵一样
//
// 1   0 1 0 0
//   +---------
// 1 | 0 1 1 1
// 1 | 1 1 2 2
// 1 | 0 0 1 0
//


public class Q221 {

    public int maximalSquare(char[][] matrix) {
        // dp二维数组的含义是以i,j为正方形右下角元素时最大的正方形边长,显然当matrix[i][j]=0时,dp[i][j]=0,matrix[i][j] = 1时,dp[i][j]至少为1
        int[][] dp = new int[matrix.length][matrix[0].length];
        int maxLength = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (i == 0 || j == 0) dp[i][j] = matrix[i][j] - 48;  // '0'的ASCII码是48
                else if (matrix[i][j] == '0') dp[i][j] = 0;

                // 这个else的含义是当前这个位置的元素为1,并且不是首行也不是首列
                else {
                    int dpLast = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
                    dp[i][j] = dpLast + 1;
                }
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
        return maxLength * maxLength;
    }

    public static void main(String[] args) {

        char[][] matrix = new char[4][5];
        matrix[0] = new char[]{'1','0','1','0','0'};
        matrix[1] = new char[]{'1','0','1','1','1'};
        matrix[2] = new char[]{'1','1','1','1','1'};
        matrix[3] = new char[]{'1','0','0','1','0'};
        Q221 q221 = new Q221();
        System.out.println(q221.maximalSquare(matrix));
    }

}
